package com.test.leetcode;

/**
 * https://leetcode.cn/problems/edit-distance/description/
 * @author sujiafa
 * @date 2025/4/9
 */
public class n72_最小编辑距离 {
    public int minDistance(String word1, String word2) {
        // 线性DP知识一例题
        int word1Length = word1.length();
        int word2Length = word2.length();
        // dp[i][j]表示将word1的前i个字符转换为word2的前j个字符所需要的最少操作数
        int[][] dp = new int[word1Length + 1][word2Length + 1];
        // 初始化编辑距离
        for (int i = 0; i < word1Length + 1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j < word2Length + 1; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i < word1Length + 1; i++) {
            for (int j = 1; j < word2Length + 1; j++) {
                // 判断一下最后一步的操作
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    // 两个字符串最后一个字符相同
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 会出现插入、删除、替换操作
                    // 插入 dp[i][j-1] + 1
                    // 删除 dp[i-1][j] + 1
                    // 替换 dp[i-1][j-1] + 1
                    dp[i][j] = Math.min(Math.min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1;
                }
            }
        }

        return dp[word1Length][word2Length];
    }
}
